import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class board {
	private List<Character[]> letters;
	private Boolean [][] passedLetters;

	//Instantiate Board with random letters
	public board(int size){
		this.letters = new ArrayList<Character[]>();
		this.passedLetters = null;

		//Official Boggle Dice Set
		Character[][] dice = new Character[16][6];
		dice[0][0] = 'A'; dice[0][1] = 'A'; dice[0][2] = 'E'; dice[0][3] = 'E'; dice[0][4] = 'G'; dice[0][5] = 'N'; 
		dice[1][0] = 'E'; dice[1][1] = 'L'; dice[1][2] = 'R'; dice[1][3] = 'T'; dice[1][4] = 'T'; dice[1][5] = 'Y'; 
		dice[2][0] = 'A'; dice[2][1] = 'O'; dice[2][2] = 'O'; dice[2][3] = 'T'; dice[2][4] = 'T'; dice[2][5] = 'W'; 
		dice[3][0] = 'A'; dice[3][1] = 'B'; dice[3][2] = 'B'; dice[3][3] = 'J'; dice[3][4] = 'O'; dice[3][5] = 'O'; 
		dice[4][0] = 'E'; dice[4][1] = 'H'; dice[4][2] = 'R'; dice[4][3] = 'T'; dice[4][4] = 'V'; dice[4][5] = 'W'; 
		dice[5][0] = 'C'; dice[5][1] = 'I'; dice[5][2] = 'M'; dice[5][3] = 'O'; dice[5][4] = 'T'; dice[5][5] = 'U'; 
		dice[6][0] = 'D'; dice[6][1] = 'I'; dice[6][2] = 'S'; dice[6][3] = 'T'; dice[6][4] = 'T'; dice[6][5] = 'Y'; 
		dice[7][0] = 'E'; dice[7][1] = 'I'; dice[7][2] = 'O'; dice[7][3] = 'S'; dice[7][4] = 'S'; dice[7][5] = 'T'; 
		dice[8][0] = 'D'; dice[8][1] = 'E'; dice[8][2] = 'L'; dice[8][3] = 'R'; dice[8][4] = 'V'; dice[8][5] = 'Y'; 
		dice[9][0] = 'A'; dice[9][1] = 'C'; dice[9][2] = 'H'; dice[9][3] = 'O'; dice[9][4] = 'P'; dice[9][5] = 'S'; 
		dice[10][0] = 'H'; dice[10][1] = 'I'; dice[10][2] = 'M'; dice[10][3] = 'N'; dice[10][4] = 'Q'; dice[10][5] = 'U'; 
		dice[11][0] = 'E'; dice[11][1] = 'E'; dice[11][2] = 'I'; dice[11][3] = 'N'; dice[11][4] = 'S'; dice[11][5] = 'U'; 
		dice[12][0] = 'E'; dice[12][1] = 'E'; dice[12][2] = 'G'; dice[12][3] = 'H'; dice[12][4] = 'N'; dice[12][5] = 'W'; 
		dice[13][0] = 'A'; dice[13][1] = 'F'; dice[13][2] = 'F'; dice[13][3] = 'K'; dice[13][4] = 'P'; dice[13][5] = 'S'; 
		dice[14][0] = 'H'; dice[14][1] = 'L'; dice[14][2] = 'N'; dice[14][3] = 'N'; dice[14][4] = 'R'; dice[14][5] = 'Z'; 
		dice[15][0] = 'D'; dice[15][1] = 'E'; dice[15][2] = 'I'; dice[15][3] = 'L'; dice[15][4] = 'R'; dice[15][5] = 'X'; 

		//Generates Random Dice Sequence
		List<Integer> unusedDice = new ArrayList<Integer>();
		for(int die = 0; die < 16; die++){
			unusedDice.add(die);
		}
		Collections.shuffle(unusedDice);
		int dieIterator = 0;
		
		for(int i = 0; i < size; i++){
			Character[] let = new Character[size];
			for(int j = 0; j < size; j++){
				let[j] = dice[unusedDice.get(dieIterator)][new Random().nextInt(6)];
				dieIterator = (dieIterator + 1) % 16;
				if(dieIterator == 0 ){
					Collections.shuffle(unusedDice);
				}
			}
			letters.add(let);
		}
	}

	//Instantiate board with given letters
	public board(List<Character[]> letters){
		this.letters = letters;
		this.passedLetters = null;
	}

	//Returns current letters in board
	public List<Character[]> getLetters(){
		return letters;
	}

	//Returns current size of board
	public int getBoardSize(){
		return letters.size();
	}

	//Returns letter at current location
	Character getLetter(int x, int y){
		return letters.get(x)[y];
	}

	//Checks if a word exists in the board
	public int wordExists(String word, Boolean saveResult){		
		word = word.toUpperCase();
		passedLetters = null;
		//Marks passed letters
		Boolean letPassed[][] = new Boolean[getBoardSize()][getBoardSize()];
		for(int i = 0; i<getBoardSize(); i++){
			for (int j = 0; j<getBoardSize(); j++){
				letPassed[i][j] = false;
			}
		}

		char[] wordLetters = word.toCharArray();
		int longestLetter = 0;
		for(int i = 0; i < getBoardSize(); i++){
			for(int j = 0; j < getBoardSize(); j++){
				if ((getLetter(i, j).equals(wordLetters[0]))){
					letPassed[i][j] = true;
					if(wordLetters.length == 1){
						passedLetters = letPassed;
						return 1;
					}
					else{ 
						int longestLet = checkAdjacent(wordLetters, 1, i, j, letPassed, false);
						longestLetter = (longestLetter < longestLet ? longestLet : longestLetter);
						if(longestLet == wordLetters.length)
							return longestLet;
						else
							letPassed[i][j] = false;
					}
				}
			}
		}
		return longestLetter;
	}

	//Checks adjacent letters
	private int checkAdjacent(char[] wordLetters, int currentLetter, int x, int y, Boolean letPassed[][], Boolean saveResult){
		int longestLetter = currentLetter;
		passedLetters = null;
		for(int i = -1 ; i <= 1 ; i++){
			for(int j = -1; j<= 1 ; j++){
				if(x+i >= 0 && y+j >= 0 && ((x+i) < getBoardSize()) && ((y+j) < getBoardSize()) && letPassed[x+i][y+j] == false){
					if(getLetter(x+i, y+j).equals(wordLetters[currentLetter])){
						letPassed[x+i][y+j] = true;
						if(wordLetters.length == (currentLetter + 1)){
							passedLetters = letPassed;
							return wordLetters.length;
						}
						else {
							int curLet = (checkAdjacent(wordLetters, currentLetter + 1, x+i, y+j, letPassed, false));
							longestLetter = (longestLetter < curLet ? curLet : longestLetter);
							if (curLet == wordLetters.length)
								return wordLetters.length;
							else
								letPassed[x+i][y+j] = false;
						}
					}
				}
			}
		}
		return longestLetter;
	}
	
	
	//Get Passed Letters
	public Boolean[][] getPassedLetters(){
		return passedLetters;
	}
}
